package linkedList;

/**
 * 删除排序链表中的重复元素 II -82
 *
 * @author yyz
 * @create 2023-11-22 15:18
 */
public class 删除排序链表中的重复元素II {
    public ListNode deleteDuplicates(ListNode p) {
        if (p == null || p.next == null) {
            // 如果链表为空或者只有一个节点，则直接返回该节点，无需进行删除操作
            return p;
        }

        if (p.val == p.next.val) {
            // 如果当前节点p的值与下一个节点p.next的值相等，则说明存在重复元素
            // 使用while循环跳过所有重复元素，找到第一个不重复的节点x
            ListNode x = p.next.next;
            while (x != null && x.val == p.val) {
                x = x.next;
            }
            // 递归调用deleteDuplicates(x)来删除后面的所有重复元素并返回结果
            return deleteDuplicates(x);
        } else {
            // 如果当前节点p的值与下一个节点p.next的值不相等，则说明不存在重复元素
            // 将p的下一个节点指向递归调用deleteDuplicates(p.next)后的结果
            // 再返回p本身。这样能够确保链表中所有重复元素都被删除，并保持链表的顺序。
            p.next = deleteDuplicates(p.next);
            return p;
        }
    }

    public ListNode deleteDuplicates2(ListNode head) {
        // 如果链表为空或只有一个节点，直接返回原链表
        if (head == null || head.next == null) {
            return head;
        }

        // 创建一个虚拟节点，并将其指向头节点
        ListNode s = new ListNode(-1, head);
        // p1、p2、p3分别表示当前节点、下一个节点和下下个节点
        ListNode p1 = s;
        ListNode p2, p3;

        // 遍历链表
        while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
            // 如果当前节点的值与下一个节点的值相同
            if (p2.val == p3.val) {
                // 找到下一个值不同的节点
                while ((p3 = p3.next) != null && p3.val == p2.val) ;
                // 将当前节点的next指针指向下一个值不同的节点
                p1.next = p3;
            } else {
                // 如果当前节点的值与下一个节点的值不同，则继续遍历
                p1 = p1.next;
            }
        }

        // 返回删除重复节点后的链表
        return s.next;
    }


    public static void main(String[] args) {
        ListNode list = ListNode.of(1, 1, 2, 3, 3);
//        ListNode list = ListNode.of();
        System.out.println(new 删除排序链表中的重复元素II().deleteDuplicates2(list));
    }
}
